package string;

import java.util.ArrayList;
import java.util.List;

public class Conclude {
    /**
     * 杨辉三角
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list= new ArrayList();
        list.add(new ArrayList<Integer>());
        list.get(0).add(1);
        for (int h = 1; h < numRows; h++) {
            List<Integer> listRow = new ArrayList();
            //设置边界为1
            listRow.add(1);
            //设里面的值
            for (int k = 1; k < h ; k++) {
                listRow.add(list.get(h - 1).get(k - 1)
                        + list.get(h - 1).get(k));
            }
            //设置边界为1
            listRow.add(1);
            //加入row
            list.add( listRow);
        }
        return list;
    }

    /**
     * 杨辉三角II
     */
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> list= new ArrayList();
        list.add(new ArrayList<Integer>());
        list.get(0).add(1);
        for (int h = 1; h < rowIndex + 1; h++) {
            List<Integer> listRow = new ArrayList();
            //设置边界为1
            listRow.add(1);
            //设里面的值
            for (int k = 1; k < h ; k++) {
                listRow.add(list.get(h - 1).get(k - 1)
                        + list.get(h - 1).get(k));
            }
            //设置边界为1
            listRow.add(1);
            //加入row
            list.add( listRow);
            if(h == rowIndex ){
                return listRow;
            }
        }
        return list.get(0);
    }

    /**
     * 反转字符串中的单词 III
     */
    public String reverseWords(String s) {
        String[] strs = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i=strs.length - 1; i>=0; i--){
            sb.append(strs[i]);
            if(i!=0){
                sb.append(" ");
            }
        }
        return sb.reverse().toString();
    }

    /**
     * 寻找旋转排序数组中的最小值
     */
    public int findMin(int[] nums) {
        int left =0, right = nums.length-1;
        //mid>left且mid<right才正常
        //mid<left:往左取
        //循环直到相差为1
        while(Math.abs(left - right) > 1) {
            if (nums[(left + right) / 2] > nums[right]){
                left = (left + right) / 2;
            }
//        if(nums[(left+right)/2] < left){
            else {
                right = (left + right) / 2;
            }
        }
        return Math.min(nums[left], nums[right]);
    }

    /**
     * 删除排序数组中的重复项
     */
    public int removeDuplicates(int[] nums) {
        //慢指针:指向可被替代的位置
        int slowp = 0;
        int fastp = 1;
        for(int i = 1; i<nums.length; i++){
            //若不等:查看slowp是否有位置
            //有位置:赋值,len不变
            if(nums[i] !=nums[i-1]){
                if(slowp != 0){
                    nums[slowp] = nums[i];
                    slowp ++;
                    fastp ++;
                }
                else{
                    fastp ++;
                }
            }
            //若相等
            else if(nums[i] ==nums[i-1] && slowp == 0){
                slowp = i;
            }

        }
        return fastp;
    }

    /**
     * 移动零
     */
    public void moveZeroes(int[] nums) {
        //遍历
        int index = 0;
        int zeroLen = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                nums[index++] = nums[i];
            }
            else{
                zeroLen++;
            }
        }
        for(int i = 0; i<zeroLen; i++){
            nums[nums.length-i-1] = 0;
        }
    }
}
